class Solution {
public:
    string largestGoodInteger(string num) {
        int n = num.size();

        // 法一：滑动窗口
        string ret;
        // for(int i = 0; i < n - 2; i++)
        //     if(num[i] == num[i + 1] && num[i] == num[i + 2])
        //         if(ret == "" || num[i] > ret[0])
        //             ret = num.substr(i, 3);
        // return ret;

        // 法二：一次遍历
        // 时间复杂度：O(nk)，其中 n 是 num 的长度，k = 3
        char mx = 0;
        // for(int i = 0; i < n - 2; i++)
        //     if(num[i] > mx && num[i] == num[i + 1] && num[i] == num[i + 2])
        //         mx = num[i];
        // return mx == 0 ? "" : string(3, mx);

        // 优化
        // 用一个计数器 cnt 记录当前匹配长度，如果长度等于 3，则更新答案的最大值。如果相邻字母不同，则重置 cnt
        // 这样可以做到完美的线性复杂度，即使题目把 3 改成其他数字，时间复杂度仍然是 O(n) 的
        int cnt = 1;
        for(int i = 1; i < n; i++)
        {
            char d = num[i];
            if(d != num[i - 1])
            {
                cnt = 1;
                continue;
            }
            cnt++;      // 遇到相同字符时，cnt++
            if(cnt == 3 && d > mx)
                mx = d;
        }
        return mx == 0 ? "" : string(3, mx);
    }
};